package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 字典序的第K小数字
 */

public class Code440 {
    public static void main(String[] args) {
        int n = 13, k = 5;
        System.out.println(new Code440().findKthNumber(n, k));
    }

    public int findKthNumber(int n, int k) {
        int prefix = 1;
        while (k > 1) {
            int count = countNodes(prefix, n);
            if (k > count) {
                prefix++;      // 切换到下一个前缀
                k -= count;
            } else {
                prefix *= 10;  // 进入子节点
                k--;
            }
        }
        return prefix;
    }

    // 计算以 prefix 为前缀的数字总数（prefix 必须 ≤ n）
    private int countNodes(long prefix, int n) {
        int count = 0;
        long next = prefix + 1;
        while (prefix <= n) {
            count += Math.min(n + 1, next) - prefix;
            prefix *= 10;
            next *= 10;
        }
        return count;
    }
}
